package com.leetcode.题库;

import com.leetcode.common.model.ListNode;

/**
 * @author 覃国强
 * @date 2022-03-03 20:19
 */
public class 题库_0147_对链表进行插入排序 {

  public static void main(String[] args) {

  }

  static
  class Solution {
    public ListNode insertionSortList(ListNode head) {
      if (head.next == null) {
        return head;
      }
      // 添加一个假头
      ListNode node = new ListNode();
      node.next = head;
      head = node;

      ListNode tail = head.next;

      while (tail.next != null) {
        // 当前需要排序的节点
        node = tail.next;
        // 如果比末尾节点值还大，不需要排序，尾节点后移
        if (node.val >= tail.val) {
          tail = tail.next;
          continue;
        }
        // 将当前节点从链表中移除
        tail.next = node.next;

        ListNode prev = head;
        ListNode pointer = head.next;
        while (pointer != tail.next) {
          // 在 pointer 前插入 node 节点
          if (node.val <= pointer.val) {
            prev.next = node;
            node.next = pointer;
            break;
          }
          // pointer 向后移动
          prev = pointer;
          pointer = pointer.next;
        }
      }
      return head.next;
    }
  }

}
